import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution139 {
    public static void main(String[] args) {
        String s = "leetcode" ;
        List<String> list = new ArrayList<>();
        list.add("leet") ; list.add("code") ;
        System.out.println(wordBreak(s , list));
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>() ;
        for(String str : wordDict){
            set.add(str);
        }
        int n = s.length() ;
        // 状态表示 : dp[i] , 以i 结束的[0 , i] 区间能不能被 dict 拼接出来
       boolean[] dp = new boolean[n+1] ;
       dp[0] = true ;   // 最前面加一个,防止 j-1越界

        // 状态转移方程 : 加一个 j , 用[0,j-1] ,[j,i] 来配合判断 [0,i] 能不能被拼接出来
        // 如果 [j,i] 区间能被 dict拼接出来, 同时 dp[0,j-1] 为true , 说明 [0,i] 这一整个能被拼接出来
        for(int i=1 ; i <= n ; i ++){
            for(int j=1 ; j <= i ; j ++){
                String ret = s.substring(j-1 , i) ;
                if(set.contains(ret) && dp[j-1] ){
                    dp[i] = true ;
                    break ;
                }
            }
        }

        return dp[n] ;
    }
}